Shortest distance to a character [Min Array]

Time: O(N); Space: O(1); easy

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = “loveleetcode”, C = ‘e’

Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Notes:

  • S string length is in [1, 10000].

  • C is a single character, and guaranteed to be in string S.

  • All letters in S and C are lowercase.

Intuition For each index S[i], let’s try to find the distance to the next character C going left, and going right. The answer is the minimum of these two values.

Algorithm When going left to right, we’ll remember the index prev of the last character C we’ve seen. Then the answer is i - prev. When going right to left, we’ll remember the index prev of the last character C we’ve seen. Then the answer is prev - i. We take the minimum of these two answers to create our final answer.

[3]:

class Solution1(object):
    def shortestToChar(self, S, C):
        """
        :type S: str
        :type C: str
        :rtype: List[int]
        """
        prev = float('-inf')
        ret = []
        for i, x in enumerate(S):
            if x == C:
                prev = i
            ret.append(i - prev)

        prev = float('inf')
        for i in range(len(S) - 1, -1, -1):
            if S[i] == C:
                prev = i
            ret[i] = min(ret[i], prev - i)

        return ret

[4]:

s = Solution1()
S = "loveleetcode"
C = 'e'
assert s.shortestToChar(S, C) == [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]